package hihocode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
import java.util.Scanner;

//一道树形博弈的题
public class Offer20Problem4 {

	private List<List<Integer>> lists = new ArrayList<>();

	public static void main(String[] args) {
		Offer20Problem4 object = new Offer20Problem4();
		object.getRes();
	}

	public void getRes() {
		Scanner scanner = new Scanner(System.in);
		int testCase = scanner.nextInt();
		HashMap<Integer, Integer> map = new HashMap<>();
		StringBuilder sBuilder = new StringBuilder();
		for (int test = 1; test <= testCase; test++) {
			map.clear();
			lists.clear();
			int nodes = scanner.nextInt();
			// n - 1条边
			for (int i = 0; i <= nodes; i++) {
				lists.add(new ArrayList<Integer>());
			}
			for (int i = 1; i < nodes; i++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();
				Integer weight = null;
				if((weight = map.get(y)) != null){
					map.put(x, weight + 1);
				}else{
					map.put(x, 1);
				}
				//存储所有的子节点
				lists.get(x).add(y);
//				lists.get(y).add(x);
			}
			int rootIndex = 1;
			int maxValue = 0;
			for(Entry<Integer, Integer> entry : map.entrySet()){
				if(entry.getValue() > maxValue){
					rootIndex = entry.getKey();
					maxValue = entry.getValue();
				}
			}
			//先手必胜态
			if (getSg(rootIndex, -1) != 0) {
				sBuilder.append(1);
			} else {
				sBuilder.append(0);
			}
			int sum = 0;
			//对于可以删除根节点而言，应该是遍历所有结点为根的情况
			for(int childrens : lists.get(rootIndex)){
				sum ^= getSg(childrens, -1);
			}
			if (sum != 0) {
				sBuilder.append(1);
			} else {
				sBuilder.append(0);
			}
		}
		System.out.println(sBuilder.toString());
		scanner.close();
	}

	private int getSg(int u, int pre) {
		int ret = 0;
		for (int i = 0; i < lists.get(u).size(); i++) {
			if (lists.get(u).get(i) != pre) {
				ret ^= (1 + getSg(lists.get(u).get(i), u));
			}
		}
		return ret;
	}
}
